Hierarchically arranged memory has been a common feature in computing for some time. Fundamentally, faster memory is more expensive per byte. Despite rapid advances in storage performance, it is often economically unsound to utilize only the lowest latency storage medium. Instead, in order to deliver acceptable performance within a fixed budget, storage devices of different sizes and speeds may be arranged so that memory transactions read or write to the fastest devices whenever possible.
In a typical example, a hierarchical memory structure includes a main memory and one or more caches. The main memory is a large pool of storage, and, for reasons including cost, is often made up of relatively slow storage devices. The main memory defines the address space and thereby defines the limits of the available storage. However, portions of the address space may be mapped to a cache, a memory pool typically utilizing a faster storage medium, so that transactions directed to mapped addresses can be read from and/or written to the faster storage medium. In multiple-tiered configurations, portions of the cache may be mapped to another cache made up of a faster storage medium. In many examples, memory structures include multiple caches, each utilizing progressively faster storage media.
A number of techniques exist for determining which address ranges to map to a particular cache. For example, principles of locality are commonly used in cache mapping. The principle of temporal locality suggests that data that has been accessed recently is likely to be accessed again. Accordingly, frequently accessed data is often cached. The principle of spatial locality suggests that data accesses tend to cluster around certain address. Accordingly, a range of addresses is often cached based on an access to an address within the range. By effectively predicting data that will be the target of subsequent transactions, more transactions can be performed by the cache even when the cache medium is significantly smaller than the main memory. However, there is a minimum cache size beyond which performance is unacceptably impacted. Unfortunately, the minimum cache size depends, in large part, on the interrelationship of the memory transactions, and no one minimum size is correct for all applications.
Storage systems, computing systems that process data transactions on behalf of other computing systems, are generally very cache-sensitive. Storage systems typically receive a large number of transactions and can experience widely varying workloads depending on host activity. These effects and others make it extremely difficult to pre-judge proper cache sizes. Further complicating matters, due to the large number of transactions, the computing cost to determine a proper cache size by analyzing real-world workloads may prove prohibitive. Accordingly, an efficient system and method for modeling a cache and determining an optimal cache size based on observed data transactions has the potential to improve cache size matching and system performance.